package arithmetic.LeetCode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import utils.TreeNode;

/**
 *437. 路径总和 III
 * 给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
 *
 * 路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
 *
 * 输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
 * 输出：3
 * 解释：和等于 8 的路径有 3 条，如图所示。
 *
 * 链接：https://leetcode.cn/problems/path-sum-iii
 *
 * @author jiangfeng on 2023/4/21
 */
public class PathSum {
    public static void main(String[] args) {
        System.out.println(new Solution().pathSum(TreeNode.createTree(new Integer[]{5,4,8,11,null,13,4,7,2,null,null,5,1}),22));
        //System.out.println(new Solution().pathSum(TreeNode.createTree(new Integer[]{10,5,-3,3,2,null,11,3,-2,null,1}),8));
        //System.out.println(new Solution().pathSum(TreeNode.createTree(new Integer[]{1000000000,1000000000,null,294967296,null,1000000000,null,1000000000,null,1000000000}),0));
    }

    static  class Solution{
            Map<Long,Integer> map;
            // 使用前缀和优化
            public int pathSum(TreeNode root, int targetSum) {
                map = new HashMap();
                // 存放结果
                map.put(0L,1);
                return dfs(root,targetSum,0);
            }

            public int dfs(TreeNode root,int targetSum,long cur){
                if(root==null){
                    return 0;
                }

                cur+=root.val;
                // 计算从当前路径到 根路径所有的路径和里有没有 符合的.
                int res = map.getOrDefault(cur-targetSum,0);

                // 将当前的合也加入.
                map.put(cur,map.getOrDefault(cur,0)+1);
                res+=dfs(root.left,targetSum,cur);

                res+=dfs(root.right,targetSum,cur);
                // 回退状态.
                map.put(cur,map.getOrDefault(cur,0)-1);
                return res;
            }
    }
    static class Solution1 {
        int result=0;
        public int pathSum(TreeNode root, int targetSum) {
            cacl(root,targetSum);
            return result;
        }

        // 思路遍历完所有树. 选任意根节点,计算该节点到叶子节点的值.
        public List<Long> cacl(TreeNode root, int targetSum) {
            if(root==null){
                return Collections.emptyList();
            }
            List<Long> r = new ArrayList();
            if(root.val==targetSum){
                result++;
            }
            r.add(Long.valueOf(root.val));
            if(root.left!=null){
                List<Long> left= cacl(root.left,targetSum);
                for(Long i:left){
                    Long v =root.val+i;
                    if(v==targetSum){
                        result++;
                    }
                    r.add(v);
                }
            }
            if(root.right!=null){
                List<Long> right= cacl(root.right,targetSum);
                for(Long i:right){
                    Long v =root.val+i;
                    if(v==targetSum){
                        result++;
                    }
                    r.add(v);
                }
            }
            return r;
        }
    }
}
